package sort.sort;

public class HeapSort extends Sort{
    private int heapSize;
    @Override
    protected void sort() {
        heapSize = array.length;
        heapify();
        while (heapSize > 1) {
            swap(0,--heapSize);
            shiftDown(0);
        }
    }
    // 对所有叶子节点进行下拉
    private void heapify() {
        for (int i = array.length / 2 -1; i >= 0 ; i--) {
            // 从最后一个根节点开始向上逐层遍历
            shiftDown(i);
        }
    }

    /**
     * 将根节点下拉到合适的位置
     * @param index
     */
    private void shiftDown(int index) {
        int half = heapSize >> 1;
        // 是根节点就循环
        while (index < half) {
            int leftIndex = (index << 1) + 1;
            Integer maxChild = array[leftIndex];
            int maxIndex = leftIndex;
            int rightIndex = leftIndex + 1;
            // 右节点大于左节点，记录最大值
            if (rightIndex < heapSize && cmp(array[rightIndex],array[leftIndex]) > 0) {
                maxChild = array[rightIndex];
                maxIndex = rightIndex;
            }
            // 根节点大于最大孩子结束shiftDown
            if (cmp(array[index],maxChild) >= 0) {break;}
            // 将根节点与孩子节点的最大值交换位置
            swap(index,maxIndex);
            // 记录最大值索引
            index = maxIndex;
        }
    }
}
